package com.zx._12_算法.剑指offer._2022;

import com.zx._12_算法.TreeNode;

/**
 * https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
 */
public class 树的子结构 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        TreeNode root = findRoot(A, B);
        if (root == null) {
            return false;
        }

        return compare(root, B);
    }

    public TreeNode findRoot(TreeNode A, TreeNode B) {
        if (A == null) {
            return null;
        }
        if (A.val == B.val &&
                ((B.left != null && A.left != null && A.left.val == B.left.val) ||
                        (B.right != null && A.right != null && A.right.val == B.right.val)
                        || (B.left == null && A.left == null))

        ) {
            return A;
        }
        TreeNode left = findRoot(A.left, B);
        TreeNode right = findRoot(A.right, B);

        return left != null ? left : (right != null ? right : null);
    }

    public boolean compare(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;
        }
        if (a == null) {
            return false;
        }

        if (a.val == b.val) {
            boolean b1 = compare(a.left, b.left);
            boolean b2 = compare(a.right, b.right);

            return b1 && b2;

        } else {
            return false;
        }
    }
}
